#include <stdio.h>
#include <stdlib.h>
// #include "myLinkList.h"//注意导入这个自己写的头文件

#define datatype int //定义元素的数据类型
struct node
{
    datatype data;     //数据域
    struct node *next; //指针域
};
typedef struct node NODE;

struct linklist
{
    NODE *head; //头结点
    int length; //链表的长度
};
typedef struct linklist LINKLIST;

/*之后下面是函数的声明，具体函数的实现要在mylinklist.c里面来实现*/

LINKLIST *init_linklist();                           //链表的初始化 ，建立一个空的链表
int insert_linklist(LINKLIST *L, int i, datatype x); /*在链表中的第i个元素之前插入新的元素x，表长加1，并返回1；不成功返回0*/
int delete_linklist(LINKLIST *L, int i);             /*删除链表中的第i个元素，表长减1，并返回1；不成功返回0*/
int location_linklist(LINKLIST *L, datatype x);      /*返回链表中值为x的元素的序号，若无，返回0 */
NODE *get_linklist(LINKLIST *L, int i);              /* 返回链表中第i个元素的结点，若i大于表长，输出提示语 */
void print_linklist(LINKLIST *L);                    //输出链表的元素

int main(int argc, char *argv[])
{
    LINKLIST *link; //这个变量为头文件里面的用户自定义类型SEQLIST
    int fanhui;     //代表各个操作函数的返回值
    int i, a;       //i循环变量,a输入的数
    NODE *p;        //用于得到求某个序号元素的结点指向

    link = init_linklist(); //初始化顺序表

    for (i = 0; i < 10; i++) //循环10次，往顺序表中插入10个数
        fanhui = insert_linklist(link, link->length + 1, (i + 1) * 10);
    printf("插入之后链表的元素为：");
    print_linklist(link);
    printf("链表的长度为：%d\n", link->length);

    printf("请输入要删除数的序号：");
    scanf("%d", &a);
    delete_linklist(link, a);
    printf("删除第%d个元素之后链表的元素为：", a);
    print_linklist(link);
    printf("链表的长度为：%d\n", link->length);

    printf("请输入要在链表查找的元素的序号：");
    scanf("%d", &a);
    p = get_linklist(link, a);
    if (p != NULL)
        printf("查找成功，第%d个元素值为：%d\n", a, p->data);

    printf("请输入要在链表查找的元素的值：");
    scanf("%d", &a);
    fanhui = location_linklist(link, a);
    if (fanhui == 0)
        printf("查找不成功，没有这个数！\n");
    else
        printf("查找成功，是第%d个数！\n", fanhui);

    system("PAUSE");
    return 0;
}

/*链表的初始化，建立一个空表*/
LINKLIST *init_linklist()
{
    LINKLIST *linklist;
    NODE *node;
    linklist = (LINKLIST *)malloc(sizeof(LINKLIST));
    node = (NODE *)malloc(sizeof(NODE));
    linklist->head = node;
    node->next = NULL;
    linklist->length = 0;
    return linklist;
}

/*在链表中的第i个元素之前插入新的元素x，表长加1，并返回1；不成功返回0*/
int insert_linklist(LINKLIST *L, int i, datatype x)
{
    if (i > L->length + 1 || i < 1)
    {
        printf("插入的位置不合法");
        return 0;
    }
    NODE *p = get_linklist(L, i - 1);
    NODE *q = (NODE *)malloc(sizeof(NODE));
    q->data = x;
    q->next = p->next;
    p->next = q;
    L->length++;
    return 1;
}

/*删除链表中的第i个元素，表长减1，并返回1；不成功返回0*/
int delete_linklist(LINKLIST *L, int i)
{
    if (i > L->length || i < 1)
    {
        printf("删除的位置不合法");
        return 0;
    }
    NODE *p = get_linklist(L, i - 1);
    NODE *q = p->next;
    p->next = q->next;
    free(q);
    L->length--;
    return 1;
}

/*返回链表中值为x的元素的序号，若无，返回0 */
int location_linklist(LINKLIST *L, datatype x)
{
    NODE *p = L->head;
    int index = 0;
    do
    {
        index++;
        p = p->next;
    } while (p != NULL && p->data != x);
    if (p == NULL)
        return 0;
    return index;
}

/* 返回链表中第i个元素的结点，若i大于表长，输出提示语 */
NODE *get_linklist(LINKLIST *L, int i)
{
    if (i > L->length)
        printf("查找位置%d大于链表的长度%d\n", i, L->length);
    NODE *p = L->head;
    int k;
    for (k = 1; k <= i; k++)
        p = p->next;
    return p;
}

//输出链表的元素
void print_linklist(LINKLIST *L)
{
    NODE *p = L->head->next;
    while (p != NULL)
    {
        printf("%5d", p->data);
        p = p->next;
    }
    printf("\n");
}
